﻿namespace LeetCodeProject._0001_1000._001_100._51_60._051;

public class Solution
{
    public IList<IList<string>> SolveNQueens(int n)
    {
        IList<IList<string>> solutions = new List<IList<string>>();
        int[] queens = new int[n];
        Array.Fill(queens, -1);
        HashSet<int> columns = new HashSet<int>();
        HashSet<int> diagonals1 = new HashSet<int>();
        HashSet<int> diagonals2 = new HashSet<int>();
        Backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    private void Backtrack(IList<IList<string>> solutions, int[] queens, int n, int row, HashSet<int> columns,
        HashSet<int> diagonals1, HashSet<int> diagonals2)
    {
        if (row == n)
        {
            var board = GenerateBoard(queens, n);
            solutions.Add(board);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (columns.Contains(i))
                {
                    continue;
                }

                int diagonal1 = row - i;
                if (diagonals1.Contains(diagonal1))
                {
                    continue;
                }

                int diagonal2 = row + i;
                if (diagonals2.Contains(diagonal2))
                {
                    continue;
                }

                queens[row] = i;
                columns.Add(i);
                diagonals1.Add(diagonal1);
                diagonals2.Add(diagonal2);
                Backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.Remove(i);
                diagonals1.Remove(diagonal1);
                diagonals2.Remove(diagonal2);
            }
        }
    }

    private IList<string> GenerateBoard(int[] queens, int n)
    {
        IList<string> board = new List<string>();
        for (int i = 0; i < n; i++)
        {
            char[] row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }

        return board;
    }
}